#include <stdio.h>
#include <stdlib.h>

typedef int HElemSet;
typedef int Position; /* 数组下标即为元素位置 */
typedef struct DHeapNode *MaxHeap;
typedef struct DHeapNode *MinHeap;
struct DHeapNode {
    HElemSet *data; /* 数据元素数组 */
    int size; /* 规模 */
    int capacity; /* 容量 */
};

void InitPQueue(MinHeap pq, int capacity);
void SiftUpD(MinHeap h, int d, Position i);
void SiftDownD(MinHeap h, int d, Position i);
void InsertD(MinHeap h, int d, HElemSet x);
HElemSet ExtractMinD(MinHeap h, int d);

int main(void) {
    MinHeap h;
    int capacity, d, n, i;
    HElemSet x;

    h = (MinHeap)malloc(sizeof(struct DHeapNode));
    scanf("%d %d", &capacity, &d);
    InitPQueue(h, capacity);
    scanf("%d", &n);
    h->size = n;
    for (i = 0; i < n; i++) { /* 注意：多叉堆下标从0开始 */
        scanf("%d", &h->data[i]); /* 读入一个最小堆 */
    }
    scanf("%d", &x);
    InsertD(h, d, x);
    printf("min = %d\n", ExtractMinD(h, d));
    for (i = 0; i < h->size; i++) { /* 输出插入、删除后的堆元素 */
        printf("%d\n", h->data[i]);
    }
    return 0;
}

void InitPQueue(MinHeap pq, int capacity) {
    pq->capacity = capacity;
    pq->size = 0;
    pq->data = (HElemSet *)malloc(sizeof(HElemSet) * capacity);
}

/* 算法6-7：多叉堆的上调操作 SiftUpD(h, d, i) */
void SiftUpD(MinHeap h, int d, Position i) {
    HElemSet elem;

    elem = h->data[i];
    while (i > 0
            && elem < h->data[(i - 1) / d]) { /* 当前结点小于其父结点 */
        h->data[i] = h->data[(i - 1) / d]; /* 将i的父结点元素下移 */
        i = (i - 1) / d; /* i指向原结点的父结点，即向上调整 */
    }
    h->data[i] = elem;
}
/* 算法6-7 结束 */

/* 算法6-8：多叉堆的下调操作 SiftDownD(h, d, i) */
void SiftDownD(MinHeap h, int d, Position i) {
    Position last, child;
    HElemSet elem;
    int k;

    last = h->size - 1; /* 这是最后一个元素的位置 */
    elem = h->data[i];
    while (1) {
        child = d * i + 1; /* child初始化为第1个孩子 */
        for (k = 2; child <= last && k <= d; k++) { /* 找所有孩子中最小的 */
            if ((d * i + k) <= last && h->data[d * i + k] < h->data[child]) {
                child = d * i + k; /* child更新为更小的孩子的位置 */
            }
        }
        if (child > last) { /* 前面for循环未执行，i是叶结点 */
            break; /* 已经调整到底，跳出循环 */
        }
        if (h->data[child] < elem) { /* 若最小的孩子比elem小 */
            h->data[i] = h->data[child]; /* 将最小的孩子结点上移 */
            i = child; /* i指向原结点的孩子结点，即向下调整 */
        } else { /* 若所有孩子都不比elem小 */
            break; /* 则找到了elem的最终位置，跳出循环 */
        }
    }
    h->data[i] = elem;
}
/* 算法6-8 结束 */

void InsertD(MinHeap h, int d, HElemSet x) {
    Position last;

    if (h->size == h->capacity) { /* 堆已满 */
        printf("错误：堆已满，无法插入。\n");
    } else {
        h->size++;
        last = h->size - 1;
        h->data[last] = x; /* 暂时将x放入最后一个元素的位置 */
        SiftUpD(h, d, last);
    }
}

HElemSet ExtractMinD(MinHeap h, int d) {
    HElemSet min_key;
    Position last;

    min_key = h->data[0]; /* 这是将要返回的最小元 */
    last = h->size - 1; /* 这是删除前最后一个元素的位置 */
    h->size--;
    h->data[0] =
        h->data[last]; /* 暂时将删除前最后一个元素放入根的位置 */
    SiftDownD(h, d, 0); /* 从根结点下调 */
    return min_key;
}